package com.engine.cn.leetcode;

import java.util.Stack;

/**
 * 有效的括号(LeetCode 20) - 判断括号字符串是否有效 示例 1：
 * 输入：s = "()"
 * 输出：true
 * 示例 2：
 * 输入：s = "()[]{}"
 * 输出：true
 * 示例 3：
 * 输入：s = "(]"
 * 输出：false
 * 示例 4：
 * 输入：s = "([])"
 * 输出：true
 */
public class StackTest {
    /**
     * 解题思路1.利用栈的特殊数据结构来解题，2.遍历字符串中的每个字符，遇到左括号时，将其压入栈中；遇到右括号时，检查栈顶元素是否与之匹配，如果匹配，弹出栈顶元素。如果不匹配或为空，则返回false
     *
     * @param s 给定的元素
     * @return boolean
     */
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                char top = stack.pop();
                if (!isMatching(top, c)) {
                    return false;
                }
            }
        }

        return stack.isEmpty();
    }

    private static boolean isMatching(char left, char right) {
        return '(' == left && ')' == right ||
                '[' == left && ']' == right ||
                '{' == left && '}' == right;
    }

    public static void main(String[] args) {
        boolean boo = isValid("()[]}");
        System.out.println(boo);
    }
}
